package l.l.w.leetcode.Sum_4;

import java.util.*;

/**
 * Created by llw on 2017/10/28.
 */
public class Sum_4 {
    public List<List<Integer>> fourSum(int[] nums, int target) {

        if(nums == null || nums.length ==0) return Collections.emptyList();
        Arrays.sort(nums);
        List<List<Integer>> result = new LinkedList<List<Integer>>();
        int n = nums.length;
        for(int i = 0; i < n-3; ++i){

            if(i >=1 && nums[i]==nums[i-1]) continue;
            int pre = Integer.MIN_VALUE;
            for(int j = i+1; j<n-2; ++j){
                if(nums[j] == pre) continue;
                pre = nums[j];
                int t = target - nums[i]-nums[j];
                int start = j+1,end = n-1;
                while(start<end){
                    int sum = nums[start]+nums[end];
                    if(sum == t){
                        ArrayList<Integer> list = new ArrayList<Integer>(4);
                        list.add(nums[i]);
                        list.add(nums[j]);
                        list.add(nums[start]);
                        list.add(nums[end]);
                        result.add(list);
                        start++;
                        end --;
                        while(start <= end && nums[start] == nums[start-1]) start++;
                        while(start <= end && nums[end] == nums[end+1]) end--;
                    }else if(sum < t){
                        start++;
                    }else{
                        end--;
                    }
                }
            }

        }
        return result;
    }

    public static void main(String[] args) {
        //[]
//        -11
        int[] nums = {1,-2,-5,-4,-3,3,3,5};
        int target = -11;
        List<List<Integer>> result = new Sum_4().fourSum(nums, target);
        System.out.println(result);
    }
}
